package java学习.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 刘世锦
 * 2022-12-15 21:30:54	 当前时间
 */
//给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并
//返回这颗 二叉树 。 
//
// 
//
// 示例 1: 
//
// 
//输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
//输出：[3,9,20,null,null,15,7]
// 
//
// 示例 2: 
//
// 
//输入：inorder = [-1], postorder = [-1]
//输出：[-1]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= inorder.length <= 3000 
// postorder.length == inorder.length 
// -3000 <= inorder[i], postorder[i] <= 3000 
// inorder 和 postorder 都由 不同 的值组成 
// postorder 中每一个值都在 inorder 中 
// inorder 保证是树的中序遍历 
// postorder 保证是树的后序遍历 
// 
// Related Topics 树 数组 哈希表 分治 二叉树 
// 👍 892 👎 0

public class 从中序与后序遍历序列构造二叉树{
	public static void main(String[] args) {
		Solution solution = new 从中序与后序遍历序列构造二叉树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {


	/** 复习  @author 刘世锦
	 *  @date  2023/2/4 15:27
	 *
	 *  中 |     左        |   中     |        右
	 *    | ins     mid-1 |   mid   |   mid+1     ine
	 *
	 *     9   3    15 20 7
	 *
	 *  后 |     左   |     右         |  中
	 *    | pos    x | x+1     poe-1 |  poe
	 *
	 *  	9  15   7  20    3
	 *
	 *  ine - mid -1 = poe-1-x-1
	 *   x = poe-1+mid-ine
	 *
	 *   mid - 1 - ins = x - pos
	 *     x = mid+pos-ins-1
	 *
	 *  构造root
	 */
//	HashMap<Integer, Integer> map = new HashMap<>();

	public TreeNode dfsByReview(int[] inorder,int ins,int ine, int[] postorder,int  pos,int poe){
		if (pos>poe){
			return null;
		}
		TreeNode node = new TreeNode();
		node.val = postorder[poe];
		int index = map.get(postorder[poe]);

		node.left = dfsByReview( inorder,ins,index-1,postorder,pos,index+pos-ins-1);
		node.right = dfsByReview( inorder,index+1,ine,postorder,index+pos-ins,poe-1);
		return  node;
	}
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder.length!=postorder.length){
			return null;
		}
		for (int i = 0; i < inorder.length; i++) {
			map.put(inorder[i],i);
		}


		return  dfsByReview(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
	}

	// 复习end




	/**
	 * 过程版：不断改进精简的过程。毕竟直接看最精简的代码会懵圈。。。
	 *         0 1 2 3 4 5
	 *           ↓
	 * 左中右   9,3,15,20,7
	 *                   ↓
	 * 左右中   9,15,7,20,3
	 *  3-1
	 *  20-4
	 *  7-5
	 *  15-2
	 *  9-0
	 *
	 *  1. 根据postorder 最后一个元素 找到其对应中序的位置k
	 *  2. 由k 区分左右子树的 中序区间:[il,ir]、后序区间:[pl,pr]。
	 * 左闭右闭：
	 *        左        中     右
	 *     |-------|-------|---------|
	 *      il   k-1   k    k+1   ir
	 *
	 *       左        右         中
	 *     |-------|-------|---------|
	 *     pl     x x+1   pr-1      pr
	 *     ∵ 左、右子树的 中序区间大小==后序区间大小
	 *     ∴  k-1-il = x - pl
	 *     故 x = k-1-il+pl
	 *
	 * 左闭右闭
	 */

	public TreeNode buildTree1(int[] inorder, int[] postorder) {
		int len  = inorder.length;
		if (len==0){
			return null;
		}
		TreeNode root = new TreeNode(postorder[len-1]);
		if (len==1) {
			return root;
		}
		return dfs(inorder,postorder,0,len-1,0,len-1);

	}
	TreeNode dfs(int[] inorder, int[] postorder,int il ,int ir , int pl,int pr){
		// 若不存在 后序区间：
		if (pl>pr) {
			return null;
		}
		int k = 0;
		// 确定根节点  后序区间[pl,pr] 的最后一元素
		TreeNode root = new TreeNode(postorder[pr]);
		// 在区间[il,ir]找到根节点对应 inorder 的位置  1.0版
		for (int i = il; i <=ir; i++) {
			if (inorder[i] == root.val){
				k = i; break;
			}
		}
		// 递归左右子树。
		// 左子树  左子树的中序区间：[il,ir] , 左子树的后序区间：[pl,pr]
		root.left = dfs(inorder,postorder,il,k-1,pl,k-1-il+pl);
		// 右子树  右子树的中序区间：[il,ir] , 右子树的后序区间：[pl,pr]
		root.right = dfs(inorder,postorder,k+1,ir,k-il+pl,pr-1);
		return root;
	}

	/**
	 * 为啥用Map：每次都去找k
	 * 干脆使用Map记录
	 *     key    --  value
	 *  后序根节点  --   在中序的位置k
	 *  之后直接取就可以了。
	 *  后序与中序都是一颗树的节点，故直接遍历中序就行
	 */
	Map<Integer,Integer> map = new HashMap<>();
	public TreeNode buildTreeDFS(int[] inorder, int[] postorder) {
		int len = postorder.length;
		if (len==0){
			return null;
		}
//		for (int i = len-1;i>=0;i--){
//			if (postorder[i]==inorder[i]){
//				map.put(postorder[i],i);
//			}
//		}
		for (int i = 0; i < len; i++) {
			map.put(inorder[i],i);
		}
		return dfs2(inorder,postorder,0,len-1,0,len-1);


    }

	private TreeNode dfs2(int[] inorder, int[] postorder, int il, int ir, int pl, int pr) {
		if (pl>pr){
			return null;
		}
		// 确定根节点  后序区间[pl,pr] 的最后一元素
		TreeNode root = new TreeNode(postorder[pr]);
		// k: root对应的中序位置
		int k = map.get(root.val);

		root.left = dfs2(inorder,postorder,il,k-1,pl,k-1-il+pl);
		root.right = dfs2(inorder,postorder,k+1,ir,k-il+pl,pr-1);
		return root;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
